package problem_everyday;

public class D2025_06_25_P2040 {
    private int binarySearchProductLower(int[] nums, int factor, long product){
        // nums从小到大排列，寻找元素与factor乘积和小于product的个数
        int left=0, right=nums.length - 1;
        if(factor > 0){
            while(right >= left){
                int mid = left + (right - left) / 2;
                if( (long )nums[mid] * factor > product){
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return right + 1;
        } else if(factor < 0){
            while(right >= left){
                int mid = left + (right - left) / 2;
                if((long) nums[mid] * factor > product){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return (nums.length - left);
        } else {
            if(product >= 0){
                return nums.length;
            } else {
                return 0;
            }
        }
    }

    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        long min_num = (long)-1e10;
        long max_num = (long)1e10;
        long v = 0;
        long lower_num = 0;
        long ans = 0;
        while(max_num >= min_num){
            v = min_num + (max_num - min_num) / 2;
            // 统计所有小于v的值的数量
            lower_num = 0;
            for(int i=0; i<nums1.length; i++){
                lower_num += binarySearchProductLower(nums2, nums1[i], v);
            }
            // 如果数量大于k，则需要进入左侧寻找
            if(lower_num >= k){
                ans = v;
                max_num = v - 1;
                /*
                * 这里存在一定的不确定性，比如实际的目标是v-1是有可能
                *
                * */
            } else {
                min_num = v + 1;
            }
        }
        return ans;
    }

    public  static void main(String[] args){
        D2025_06_25_P2040 p = new D2025_06_25_P2040();
        int[] nums1 = new int[50000];
        int[] nums2 = new int[50000];
        for(int i=0; i<50000; i++){
            nums1[i] = nums2[i] = 90000 + i / 5;
        }
        nums1[50000 - 1] = 100000;
        nums2[50000 - 1] = 100000;
        long k = 2500000000L;
        long product = p.kthSmallestProduct(nums1, nums2, k);
        System.out.println(product);
    }

}
